/*
 * Copyright (c) 2018-2023 北京华恒盛世科技有限公司
 * QUICKPOOL is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *     http://license.coscl.org.cn/MulanPSL2
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PSL v2 for more details.
*/

/**
 * @file   hash.c
 * @brief  Defines functions about hash table handling.
 * @note   Use hash table to speed up search element.
 */

#include "hash.h"

static unsigned long hash_string(const char *key, int size);
static int rehash(HASH_TABLE_T *hash_table, int size);
static int get_size_from_primes(int size);


/**
 * @brief        To make a hash table
 *
 * @param[in]    size   #1: Initialized size of the hash table
 *
 * @retval       Not NULL      #1: Pointer of the hash table
 * @retval       NULL          #2: Failed to make the hash table
 *
 * @note         errno is set when allocate memory failed.
 */
HASH_TABLE_T *
gf_hash_make(int size)
{
    HASH_TABLE_T *hash_table_p;

    size = get_size_from_primes(size);

    hash_table_p = (HASH_TABLE_T *)calloc(1, sizeof(HASH_TABLE_T));
    if (NULL == hash_table_p) {
        return (NULL);
    }

    hash_table_p->size = size;
    hash_table_p->hash = (LIST_T **)calloc(hash_table_p->size, sizeof(LIST_T *));
    if (NULL == hash_table_p->hash) {
        return (NULL);
    }

    return (hash_table_p);
} /* gf_hash_make */


/**
 * @brief      Free up the hash table
 *
 * @param[in]  hash_table     #1: Hash table to be freed
 * @param[in]  func           #2: Pointer of function that is to free up element in the hash table.
 *
 * @note       Pointer of function could be NULL
 */
void
gf_hash_free(HASH_TABLE_T *hash_table, void (*func)(void *))
{
    uint32_t i;

    if (NULL == hash_table) {
        return;
    }

    for (i = 0; i < hash_table->size; i++) {
        HASH_ENTITY_T   *hash_entity_p;

        if (NULL == hash_table->hash[i]) {
            continue;
        }

        while (NULL != (hash_entity_p = (HASH_ENTITY_T *)gf_list_pop(hash_table->hash[i]))) {
            if (NULL != func) {
                (*func)(hash_entity_p->entity);
            }

            free(hash_entity_p->key);
            free(hash_entity_p);
        }

        gf_list_free(hash_table->hash[i], NULL);
    } /* for(i = 0; ...) */

    hash_table->numElements = 0;
    if (NULL != hash_table->hash) {
        free(hash_table->hash);
    }

    free(hash_table);

    return;
} /* gf_hash_free */


/**
 * @brief       Install an element to the hash table.
 *
 * @param[in]   hash_table    #1: Pointer of the hash table.
 * @param[in]   key           #2: Unique key to distinguish an element in the hash table.
 * @param[in]   element       #3: Pointer of the element to be installed to the hash table.
 *
 * @retval      Not NULL    #1: Pointer of the element to be installed.
 * @retval      NULL        #2: Failed to install the element.
 *
 * @note        Callers are supposed to check first if the element does or does not exist.
 */
void *
gf_hash_install(HASH_TABLE_T *hash_table, const char *key, void *element)
{
    unsigned long   index;
    HASH_ENTITY_T    *hash_entity_p;

    if (hash_table == NULL) {
        return (NULL);
    }

    if (hash_table->numElements >= 1.5 * hash_table->size) { /* Hash table is nearly full */

        /* Enlarge the hash table. */
        if (0 > rehash(hash_table, 2 * hash_table->size)) {
            return (NULL);
        }
    }

    /* Get the index according to the hash key */
    index = hash_string(key, hash_table->size);

    /* Create the hash entry for the element */
    hash_entity_p = (HASH_ENTITY_T *)calloc(1, sizeof(HASH_ENTITY_T));
    if (NULL == hash_entity_p) {
        return (NULL);
    }

    hash_entity_p->key = strdup(key);
    if (NULL == hash_entity_p->key) {
        return (NULL);
    }

    hash_entity_p->entity = element;

    /* If this slot is NULL initialiaze it */
    if (NULL == hash_table->hash[index]) {
        hash_table->hash[index] = gf_list_make("ulist");
    }

    hash_table->numElements++;
    gf_list_insert(hash_table->hash[index], hash_table->hash[index]->forw, (LIST_T *)hash_entity_p);

    return (hash_entity_p->entity);
} /* gf_hash_install */


/**
 * @brief    Remove an element from the hash table
 *
 * @param[in]   hash_table      #1: Pointer of the hash table.
 * @param[in]   key             #2: Unique key to distinguish an element in the hash table.
 *
 * @retval      Not NULL      #1: Pointer of element that is removed from the hash table
 * @retval      NULL          #2: Failed to remove the element, or no such element in the hash table.
 *
 * @note       We return NULL if there is no such element in the hash table.
 */
void *
gf_hash_remove(HASH_TABLE_T *hash_table, const char *key)
{
    unsigned long index;
    HASH_ENTITY_T *hash_entity_p;

    /* Get the index according to the hash key */
    index = hash_string(key, hash_table->size);

    if (NULL == hash_table->hash[index]) { /* No element */
        return (NULL);
    }

    for (hash_entity_p = (HASH_ENTITY_T *)hash_table->hash[index]->forw;
         hash_entity_p != (void *)hash_table->hash[index];
         hash_entity_p = hash_entity_p->forw) {
        if (strcmp(hash_entity_p->key, key) == 0) {
            void *element;

            /* Remove the element from the hash table*/
            gf_list_remove(hash_table->hash[index], (LIST_T *)hash_entity_p);
            element = hash_entity_p->entity;
            free(hash_entity_p->key);
            free(hash_entity_p);
            hash_entity_p = NULL;
            hash_table->numElements--;

            return (element);
        }
    }

    /* Did not find the element in the hash table */
    return (NULL);
} /* gf_hash_remove */


/**
 * @brief         To find an element in the hash table.
 *
 * @param[in]     hash_table   #1: Pointer of the hash table
 * @param[in]     key          #2: Unique key to distinguish an element in the hash table
 *
 * @retval        Not NULL     #1: Pointer of element in the hash table.
 * @retval        NULL         #2: No such element in the hash table.
 *
 * @note          We return NULL if we cannot find the element in the hash table.
 */
void *
gf_hash_find(HASH_TABLE_T *hash_table, const char *key)
{
    unsigned long index;
    HASH_ENTITY_T *hash_entity_p;

    if (hash_table == NULL || key == NULL) {
        return (NULL);
    }

    index = hash_string(key, hash_table->size);

    if (NULL == hash_table->hash[index]) { /* No element */
        return (NULL);
    }

    for (hash_entity_p = (HASH_ENTITY_T *)hash_table->hash[index]->back;
         hash_entity_p != (void *)hash_table->hash[index];
         hash_entity_p = hash_entity_p->back) {
        if (0 == strcmp(hash_entity_p->key, key)) { /* Find the element */
            return (hash_entity_p->entity);
        }
    }

    /* Cannot find the element in the hash table. */
    return (NULL);
} /* gf_hash_find */


/**
 * @brief        Initialize structure of HASH_WALK_T to walk through each element in the hash table.
 *
 * @param[in]    hash_table      #1: Pointer of the hash table.
 * @param[in]    walk            #2: Pointer of walking through the hash table.
 *
 * @note         Should be called before we walk through the hash table.
 */
void
gf_hash_walk_start(HASH_TABLE_T *hash_table, HASH_WALK_T *walk)
{
    walk->pos = 0;
    walk->hashEntity = NULL;
    walk->hashTable = hash_table;
} /* gf_hash_walk_start */


/**
 * @brief       Initialize structure of HASH_WALK_T unlink it from a hash table.
 *
 * @param[in]   walk    #1: Pointer of walking through the hash table.
 *
 * @note        Should be called after we walk through a hash table.
 */
void
gf_hash_walk_end(HASH_WALK_T *walk)
{
    memset(walk, 0, sizeof(HASH_WALK_T));
} /* gf_hash_walk_end */


/**
 * @brief        To go through each element in the hash table.
 *
 * @param[in]    walk   #1: Pointer of walking through the hash table.
 *
 * @retval       Not NULL   #1: One of element in the hash table.
 * @retval       NULL       #2: Input parameter is not valid.
 *                              Finish walking through elements in the hash table.
 *
 * @note         Should call gf_hash_walk_start before calling this function.
 *               Should call gf_hash_walk_end after calling this function.
 */
void *
gf_hash_walk(HASH_WALK_T *walk, char **key)
{
    LIST_T *list_p;
    HASH_ENTITY_T *hash_entity_p;

    if (NULL == walk || NULL == walk->hashTable) {
        return (NULL);
    }

    /* Walk on the slots */
    while (walk->pos < walk->hashTable->size) {

        list_p = walk->hashTable->hash[walk->pos];

        /* The slot has not been allocated or it is empty */
        if ((NULL == list_p) || (0 == LIST_NUM_ENTS(list_p))) {

            walk->pos++;
            /* Do this so if the entry was removed the iterator does not carry invalid memory */
            walk->hashEntity = NULL;

            continue;
        }

        /* Point the iterator to the list of objects on this slot */
        if (NULL == walk->hashEntity) {
            walk->hashEntity = (HASH_ENTITY_T *)list_p->back;
        }

        /* We have reached the end of the objects linked on this slot. Move to the next slot. */
        if (walk->hashEntity == (void *)list_p) {

            walk->hashEntity = NULL;
            walk->pos++;

            continue;
        }

        /* We have found an object on this slot, return it to the caller */
        hash_entity_p = walk->hashEntity;

        /* Move ahead to the next object */
        walk->hashEntity = hash_entity_p->back;

        if (key != NULL) {
            *key = hash_entity_p->key;
        }
        return (hash_entity_p->entity);
    } /* while (walk->pos < walk->hashTable->size) */

    return (NULL);
} /* gf_hash_walk */


/**
 * @brief       Get the hash index according to the hash key.
 *
 * @param[in]   key       #1: the hash key.
 * @param[in]   size      #2: the size of the hash array.
 *
 * @retval      h % size  #1: the hash index of the hash key.
 */
static unsigned long
hash_string(const char *key, int size)
{
    register unsigned long hash = 0;

    for(; *key; ++key) {
        register unsigned long generation;

        hash <<= 4;
        hash += *key;
        if ((generation = hash & 0xF0000000)) {
            hash ^= generation >> 24;
        }
        hash &= ~generation;
    }

    return (hash % size);
} /* hash_string */


/**
 * @brief      Enlarge the size of the hash table.
 *
 * @param[in|out]  hash_table      #1: the hash table
 * @param[in]      size            #2: the new size of the hash table
 *
 * @note       We create a new hash table and copy the element from old hash table to the new one.
 */
static int
rehash(HASH_TABLE_T *hash_table, int size)
{
    uint32_t i;
    LIST_T **list_p;
    HASH_TABLE_T tmp_hash_table;

    memset(&tmp_hash_table, 0, sizeof(HASH_TABLE_T));

    tmp_hash_table.size = get_size_from_primes(size);

    list_p = (LIST_T **)calloc(tmp_hash_table.size, sizeof(LIST_T *));
    if (NULL == list_p) {
        return (-1);
    }

    tmp_hash_table.hash = list_p;

    /* Copy element from old hash table to the temp hash table, then remove the old hash table. */
    for (i = 0; i < hash_table->size; i++) {
        HASH_ENTITY_T *hash_entity_p;

        if (NULL == hash_table->hash[i]) {
            continue;
        }

        while ((hash_entity_p = (HASH_ENTITY_T *)gf_list_pop(hash_table->hash[i]))) {
            gf_hash_install(&tmp_hash_table, hash_entity_p->key, hash_entity_p->entity);
            free(hash_entity_p->key);
            free(hash_entity_p);
        }
        gf_list_free(hash_table->hash[i], NULL);
    }

    /* Replace old hash table with the new one. */
    if (NULL != hash_table->hash)
        free(hash_table->hash);

    hash_table->hash = list_p;
    hash_table->size = tmp_hash_table.size;
    hash_table->numElements  = tmp_hash_table.numElements;

    return (0);
} /* rehash */


/**
 * @brief           Get the hash table size from the primes[]
 *
 * @param[in] size     #1: Size of the hash table
 *
 * @retval    size     #1: Size in primes[]
 */
static int
get_size_from_primes(int size)
{
    int i;
    int num_prime;
    int primes[] = { 13, 31, 53, 101, 293, 691, 941, 1427, 2153, 2953, 3769,
                     4637, 5483, 6337, 7237, 8167, 9049, 9931, 10891,
                     11897 , 12791, 13729, 14737, 15647, 16649, 17609,
                     18553, 19609, 20627, 21599, 22613, 23599, 24571,
                     25643, 26683, 27739, 28687, 29753, 30841, 31883,
                     32887, 33851, 34897, 36007, 37013, 38119, 39181,
                     40231, 41333, 42331, 43399, 44501, 45587, 46687,
                     47779, 48859, 49921, 51043, 52067, 53171, 54319,
                     55381, 56473, 57467, 58543, 59617, 60761, 61933,
                     63073, 64151, 65323, 66449, 67499, 68669, 69857,
                     70949, 71983, 73061, 74231, 75353, 76493, 77587,
                     78779, 79873, 80989, 82039, 83227, 84391, 85531,
                     86689, 87793, 89051, 90073, 91249, 92387, 93479,
                     94603, 95717, 96851, 98081, 99223, 111697, 123377,
                     135193, 147011, 158909, 171077, 183119, 195197,
                     200003, 312371, 453659, 532159, 652261, 773393,
                     868531, 978727, 1000003, 1556003, 2000003, 4000093,
                     8000099, 16000097, 1437356741, 2147483647 };

    num_prime = sizeof(primes) / sizeof(primes[0]);

    for (i = 0; i < num_prime; i++) {
        if (size <= primes[i]) {
            size = primes[i];
            break;
        }
    }

    if (i == num_prime) {
        size = primes[num_prime - 1];
    }

    return (size);

} /* get_size_from_primes */
